use std::{collections::HashMap, vec};

/// https://leetcode.cn/problems/two-sum/description/?envType=study-plan-v2&envId=top-100-liked
/// 1. 两数之和：
/// 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。
///
/// TIP: 对于需要回查的数据考虑使用hash表，二分查找，可以使回查阶段的查询时间消耗降低
pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
    let mut map = HashMap::new();
    for (i, v) in nums.iter().enumerate() {
        if map.contains_key(&(target - v)) {
            return vec![i as i32, map[&(target - v)]];
        }
        map.insert(v, i as i32);
    }
    return vec![];
}

#[test]
pub fn test_two_sum() {
    println!("{:?}", two_sum(vec![1, 3, 5, 6, 7], 6));
}

/// https://leetcode.cn/problems/group-anagrams/description/?envType=study-plan-v2&envId=top-100-liked
/// 49. 字母异位词分组
/// 给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
/// 字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
pub fn group_anagrams(strs: Vec<String>) -> Vec<Vec<String>> {
    let mut map = HashMap::new();
    let to_anagrams_vec = |a: &String| {
        let mut vec = vec![0; 26];
        for cha in a.chars() {
            vec[cha as usize - 'a' as usize] = 1;
        }
        vec
    };

    strs.into_iter().for_each(|word| {
        let ana_vec = to_anagrams_vec(&word);
        map.entry(ana_vec)
            .and_modify(|e: &mut Vec<String>| e.push(word.clone()))
            .or_insert(vec![word]);
    });
    map.into_iter().map(|(_, v)| v).collect()
}

#[test]
pub fn test_group_anagrams() {
    let x = vec!["eat", "tea", "tan", "ate", "nat", "bat"]
        .iter()
        .map(|s| s.to_string())
        .collect::<Vec<String>>();
    println!("{:?}", group_anagrams(x));
}

